Data stored on magnetic media, such as a magnetic disks, are typically stored in encoded form, so that errors in the stored data can possibly be corrected. The errors may occur, for example, because of inter-symbol interference, a defect in the disk, or noise. As the density of the data stored on the disk increases, more errors are likely, and the system is required to correct greater numbers of errors, which include greater numbers of burst errors. A burst error is typically defined as a contiguous number of symbols in which the first symbol and the last symbol are erroneous. The speed with which the system corrects the errors, including the burst errors, is important to the overall speed with which the system processes the data.
Prior to recording, multiple-bit data symbols are encoded using an error correction code (ECC). When the data symbols are retrieved from the disk and demodulated, the ECC is employed to, as the name implies, correct the erroneous data.
Specifically, before a string of k data symbols is written to a disk, it is mathematically encoded using an (n, k) ECC to form n-k ECC symbols. The ECC symbols are then appended to the data string to form an n-symbol error correction code word, which is then written to, or stored, on the disk. When the data are read from the disk, the code words containing the data symbols and ECC symbols are retrieved and mathematically decoded. During decoding, errors in the data are detected and, if possible, corrected through manipulation of the ECC symbols [for a detailed description of decoding see, Peterson and Weldon, Error Correction Codes, 2nd Ed. MIT Press, 1972].
To correct multiple errors in strings of data symbols, the system typically uses an ECC that efficiently and effectively utilizes the various mathematical properties of sets of symbols known as Galois fields. Galois fields are represented "GF (P.sup.M)", where "P" is a prime number and "M" can be thought of as the number of digits, base "P", in each element or symbol in the field. P usually has the value 2 in digital computer and disk drive applications and, therefore, M is the number of bits in each symbol. The ECC's commonly used with the Galois Fields are Reed Solomon codes or BCH codes.
Reed Solomon and BCH decoding operations involve a plurality of division operations. One method of dividing a Galois field element A by a Galois field element B is to determine the multiplicative inverse, B.sup.-1, of B and then multiply A by B.sup.-1. In prior systems a look-up table is typically used to determine the multiplicative inverse, so that the system need not perform a known, time-consuming series of steps to produce the inverse. The look-up table contains 2.sup.m -1 entries. For systems using GF(2.sup.8), that is, using 8-bit symbols, the look-up table has 2.sup.8 -1, or 255, entries.
As the density of the data increases, larger Galois Fields are used to produce the longer data codewords that are required to protect the data. Consequently, larger look-up tables are required to provide the multiplicative inverses. For GF(2.sup.10) or GF(2.sup.12), for example, the required tables have 1023 and 4095 entries, respectively. Each of the tables thus consumes a great deal of storage space, which for some systems is too expensive and/or impractical. Accordingly, what is needed is a mechanism that, without being overly complex, relatively quickly calculates the multiplicative inverses, and thus, eliminates the need for the look-up table.